This patent application is also related to a patent application entitled xe2x80x9cSelf-Organizing Distributed Appliances,xe2x80x9d filed on the same day as the present application, the entire disclosure of which is hereby incorporated herein by reference. The router described herein may be appliances of the type described in this related patent application.
The present invention relates to improved replica routing techniques and dynamic server organization.
In a dynamic server organization system, server requests are originated by client computers (clients). Programs such as browsers on these client computers originate service requests, using the HTTP protocol, in response to end user actions. These service requests are sent to network servers. For example, www.nasdaq.com is an example of such a network server on the Internet. In the system described herein, certain of the network servers are routers. Many types of devices can participate in the system we describe, including network appliances. We will use the terms client computer or browser to refer to any type of system that originates service requests.
Routers serve two functions. The first function of a router is to redirect service requests to other routers that are more suitable to service the request than the router that received the request. The second function of a router is to directly service requests by interpreting and performing the actions contained in the request. We will say that a router services a request when it directly performs a request and returns the result to the computer that sent the service request message. We will say that a router routes a request when it redirects a request to another router for processing. The entire process of deciding which router will service a request is called request routing.
In a hierarchy of routers, request routing can be performed in a restrictive or open manner. Restrictive request routing limits the routers that service a request, in order to optimize network performance. For example, a router may be required to be on the same local area network as the client computer in order to be permitted to service requests from the client. If all routers are operating, a restrictive policy can be used to optimize a desired performance metric. If not all routers are functioning, however, a restrictive policy can reduce the probability that a request can be serviced. Open routing is less restrictive and permits more routers to service a request. For example, any router that is within two network hops of a client may be permitted to service a request. While open routing increases the chances that a request can be serviced, it may not optimize a desired performance metric. One of the contributions of the present invention is a mechanism for combining the best elements of restrictive and open policies for request routing.
U.S. patent application Ser. No. 08/779,770, filed Jan. 7, 1997 entitled xe2x80x9cReplica Routing,xe2x80x9d now U.S. Pat. No. 6,052,718 the entire disclosure of which is hereby incorporated herein by reference, discloses replica routing techniques.
It is known to provide statically configured hierarchal network services such as network time protocol (NTP) that use a hierarchial organization to disseminate information (such as time distribution) through the hierarchy so that a root server (which in NTP is a server attached to an atomic clock) is not overloaded with requests.
One aspect of the invention provides a system and method of routing requests received from client computers. A router receives a request from a client computer for data. The address from which the request purports to originate is compared with coverage zone information for the router that received the request and a hierarchy of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request. If the router that received the request is not within a preferred coverage zone as identified in the previous step, the processor is redirected to a router for which the address is within the preferred coverage zone. If a router is not identified for which the address is within a preferred coverage zone, but a router other than the router that received the request is identified for which the address is within a regular coverage zone, the processor is redirected to the router for which the address is within the regular coverage zone.
According to another aspect of the invention, a message is transmitted from a router behind a firewall to a router outside the firewall. The message includes an address of the router behind the firewall. At the router outside the firewall, an apparent source address of the message is compared with the address contained in the message. If the apparent source address fails to match the address contained in the message, information is stored associating the apparent source address and the address contained in the message. At the router outside the firewall, a request is received from a processor for data, and an apparent source address of the request is identified as corresponding to the address contained in the previously received message, based on the stored information. The processor is redirected to the address contained in the previously received message.
According to another aspect of the invention, A) a server, such as a router, in a hierarchy receives a query from a server to be registered and B) sends identification of its children to the server to be registered. C) One of the server that received the query and its children is selected on the basis of its expected online performance with the server to be registered. If the selected server is the server that received the query, D) the server to be registered is attached to the server that received the query. If the selected server is one of the children, E) a query is sent from the server to be registered to the selected server and steps A-E are repeated.
According to another aspect of the invention, a server, such as a router, in a hierarchy is identified to which a server to be registered should be attached. It is determined whether there is a firewall between the server to be registered and the server to which it is to be attached. If there is no firewall between the server to be registered and the server to which it is to be attached, the server to be registered is attached directly to the server to which it is to be attached. If there is a firewall between the server to be registered and the server to which it is to be attached, it is determined whether the server to be registered should be a primary server behind the firewall. If it is determined that the server to be registered should be the primary server behind the firewall, the server to be registered is attached directly to the server to which it is to be attached. If it is determined that the server to be registered should not be the primary server behind the firewall, the server to be registered is attached indirectly to the server to which it is to be attached by attaching it to the primary server behind the firewall, which is attached directly to the server to which the server to be registered is to be attached.
According to another aspect of the invention, a first request is received at a router from a processor for data. The router serves the first request. An address from which the request purports to originate is compared with coverage zone information for the router that received the request and a hierarchy of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request, in order to identify one of the routers as a preferred router for serving the processor. The router that received and processed the first request receives a subsequent request from the processor for data. The processor is redirected to the preferred router for serving the subsequent request.
The routing technology provided by the present invention is especially useful for incorporation into appliance-like devices of the type described in the above-mentioned application entitled xe2x80x9cSelf-Organizing Distributed Appliances.xe2x80x9d Such appliances do not require manual administration, which would make the appliances expensive to maintain. The present invention allows these appliances to self-organize into routing hierarchies that can provide superior results as compared with manually administered appliances.